package str;

import java.util.Arrays;

/**
 * @ Author     ：侯耀祖
 * @ Description：
 */
public class repeatedSubstringPattern {
    public boolean repeatedSubstringPattern(String s) {
        int[] a = new int[s.length()];
        int[] next = getNext(a, s);
        int len = s.length();
        return next[len - 1] != 0 && (len % (len - next[len - 1]) == 0);
    }
    public int[] getNext(int[] next, String s){
        //i后缀末尾位置
        //j前缀末尾
        int j = 0;
        next[0] = j;
        for (int i = 1; i < s.length(); i++) {
            while (j > 0 && s.charAt(i)!=s.charAt(j)){
                j = next[j-1];
            }
            if (s.charAt(i) == s.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
